#include <iostream>
#include <vector>

int dp_fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    // 牺牲一点内存保存已经求过的值
    std::vector<int> knownArr(n + 1);
    
    // 从1开始, 与输入的数字代表的位置含义一致
    knownArr[1] = 1; 
    knownArr[2] = 1;
    for (size_t i = 3; i <= n; ++i) {
        knownArr[i] = knownArr[i-1] + knownArr[i-2];
        std::cout << knownArr[i] << " ";
    }
    return knownArr[n];
}

int dp2_fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    // 先确认前三个, 再充 0 扩大
    std::vector<int> knownArr = {0, 1, 1};
    knownArr.resize(n + 1);
    
    // std::vector<size_t>::iterator
    auto p = knownArr.begin() + 2;
    for (; p!=knownArr.end(); p++) {
        *p = *(p-1) + *(p-2);
    }
    return knownArr[n];
}

int main(){
    int n;
    std::cout << "请输入要计算的斐波那契数的位置：";
    std::cin >> n;

    if (n < 0) {
        std::cout << "请输入一个非负整数。" << std::endl;
    } else {
        int result = dp2_fibonacci(n);
        std::cout << "第" << n << "个斐波那契数是：" << result << std::endl;
    }

    return 0;
}